package Class.Method.Recursion;

import java.util.Stack;

/**
 * @author yicixingchen
 * @version 1.0
 * Create by 2022/10/18 21:03
 */

public class HanoiNonRecursion {
    public static void main(String[] args) {
            hanoi(3,"A","C","B");
    }

    public static void move(State state) {
        System.out.printf("把第%d号盘子从%s移动到%s\n", state.no, state.from, state.to);
    }

    public static void hanoi(int no, String from, String to, String by) {
        Stack<State> states = new Stack<>();
        State state = new State(no, from, to, by, false);
        states.push(state);
        while (!states.isEmpty()) {
            if (states.peek().title)
                move(states.pop());
            else {
                State pop = states.pop();
                if (pop.no == 1)
                    move(pop);
                else {
                    State currentA_B = new State(pop.no - 1, pop.from, pop.by, pop.to, false);
                    State currentA_C = new State(pop.no, pop.from, pop.to, pop.by, true);
                    State currentB_C = new State(pop.no - 1, pop.by, pop.to, pop.from, false);
                    states.push(currentB_C);
                    states.push(currentA_C);
                    states.push(currentA_B);
                }
            }
        }
    }
}

class State {
    public int no;
    public String from;
    public String to;
    public String by;
    public boolean title;

    public State(int no, String from, String to, String by, boolean title) {
        this.no = no;
        this.from = from;
        this.to = to;
        this.by = by;
        this.title = title;
    }
}
